1. Field of the Invention
The present invention relates to a frequency based method and system, and, more particularly, to a frequency based method and system for scheduling jobs with hard constraints.
2. Description of the Related Art
Suppose there are n jobs to be completed. Each job i (where i=1 to n) is characterized by two parameters: τi, the duration of job i (hereinafter referred to as “duration time”) and μi, the maximum amount of time that can transpire between consecutive performances of job i (hereinafter referred to as “revisit time”). The n jobs are to be completed by a single processor. There is no preemption. Preemption is a scheduling technique in which a server alternates between a plurality of different pending job requests, servicing portions of each job request until eventually all of the job requests are complete. Further, setups are instantaneous. In other words, each job begins instantaneously without any setup time. A schedule is feasible if every job i can be performed again no more than μi seconds after it was last performed. The revisit time μi is a hard constraint (i.e., it cannot be violated). An issue arises whether an infinite horizon feasible schedule exists for a given instance of this problem (hereinafter referred to as a “feasible scheduling problem”).
One example of the feasible scheduling problem is the pinwheel problem. If all τi (i.e., τ1 to τN) are equal to 1, then the feasible scheduling problem becomes a “pinwheel problem.” The pinwheel problem is concerned with communication between n transmitters and a common receiver. The receiver can only receive one signal at a time and the transmitters do not receive feedback about whether a transmission has been received. To guarantee that a signal is received, each transmitter repeatedly transmits a signal. The duration of time that it takes the receiver to process a signal is the same for all signals. It can be shown that no instance of the pinwheel problem can be scheduled if:
  ρ  =                    ∑                  i          =          1                n            ⁢              1                  1          +                      μ            i                                >    1.  
Holte, Rosier, Tulchinsky, and Varvel show that any instance with ρ<0.5 can be scheduled in polynomial time. See R. Holte, L. Rosier, I. Tulchinsky, and D. Varvel, “Pinwheel Scheduling with Two Distinct Numbers,” Theoretical Computer Science (1992) 100 pp. 105-135; R. Holte, L. Rosier, I. Tulchinsky, and D. Varvel, “The Pinwheel: A Realtime Scheduling Problem,” Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences (1989) pp. 693-702. Chan and Chin improve this result by showing that polynomial time can be achieved with
  ρ  <      2    3  and ρ<0.7 in two consecutive papers. See M. Y. Chan and F. Chin, “General Schedulers for the Pinwheel Problem Based on Double Integer Reduction,” IEEE Transactions on Computers (1992) 41 pp. 755-768; M. Y. Chan and F. Chin, “Schedulers for Larger Classes of Pinwheel Instances,” Algorithmica (1993) 9 pp. 425-462. Chan and Chin use a technique known as integer reduction, where an instance that is not known to have a feasible schedule is reduced to one that is known to have a feasible schedule. For only three distinct numbers, Lin and Lin prove a similar result for ρ<0.83. See S. S. Lin and K. J. Lin, “A Pinwheel Scheduler for Three Distinct Numbers with a Tight Schedulability Bound,” Algorithmica (1997) 19 pp. 411-426.
Although the pinwheel problem is a common example of the feasible scheduling problem, an ideal solution should solve any type of feasible scheduling problem. In other words, the ideal solution would find a feasible schedule of visits for n jobs for all τi, and μi in which a feasible schedule is possible. Although several solutions exist, the solutions are not ideal because, for example, they are computationally impractical or they fail to find a feasible schedule of visits in many instances when a feasible schedule is possible.
One solution is the Dynamic Programming (“DP”) approach. The DP approach is an iterative approach. If all τi and μi are rational numbers, the DP approach will converge after a finite number of steps. Here it is assumed, without loss of generality, that all τi and μi are integers. The DP approach makes use of residual vectors to first test for feasibility, then to recreate the feasibility schedule if one exists for given values of τi and μi. The DP algorithm is provided below in pseudo-code.                1. Define a vector valued function W and let V0=0 and W=0 for all {right arrow over (x)}εX. Let n=0.        2. For all {right arrow over (x)}εX:        
            V              n        +        1              ⁡          (                        x          →                N            )        =      {                                                      -              1                        ,                                                            ⁢                                                            if                  ⁢                                                                          ⁢                                                            V                      n                                        ⁡                                          (                                                                        x                          →                                                C                                            )                                                                      =                                                                            -                      1                                        ⁢                                                                                  ⁢                    or                    ⁢                                                                                  ⁢                                                                  x                        →                                            N                                                        =                                                            g                      ⁢                                                                                          ⁢                      or                      ⁢                                                                                          ⁢                                                                        x                          →                                                C                                                              =                    g                                                              ;                                                                                      -              0                        ,                                                            ⁢                          otherwise              .                                                          3. If V({right arrow over (x)})=W({right arrow over (x)}) for all {right arrow over (x)}εX go to step 4. Otherwise, set W({right arrow over (x)})=V({right arrow over (x)}) and go to step 2.        4. If V({right arrow over (x)})=−1 for all {right arrow over (x)}εX, then the problem does not have a feasible schedule. Otherwise, the feasible schedule is among the V({right arrow over (x)})=0. To find this schedule, one needs only to trace the schedule through until all the stations have been visited at least once and a particular station is revisited.        
Determining a feasible schedule iteratively using the DP approach may require an exponential amount of time. The DP approach considers all the possible residual values that can be generated. As the number of jobs i increases, the number of residual vectors increases exponentially. Such a drain on resources is a flaw with DP. More particularly, the DP approach suffers from Bellman's “curse of dimensionality” (i.e., by increasing the dimensionality of a problem, the amount of resources that one needs to solve the problem increases exponentially). Thus, the DP approach would exhaust the resources of any computer while trying to computer a schedule for a relatively small number of jobs i. Accordingly, computing a schedule using the DP approach for a large number of jobs i would be impractical, if not impossible.
Because an exact algorithm is not practical for an NP-hard problem, heuristic approaches have been developed. Two well known examples of heuristic scheduling are the Due Date approach and the Critical Ratio approach. The Due Date approach naively selects the location with the smallest residual time from the residual vector. The problem with this approach is that the location with the smallest residual time may have the most danger of not being visited before μi transpires. Furthermore, the Due Date approach does not make use of the information contained in τi or μi. For an approach to be successful, it must make use of all of the information available at the time the decision is to be made. The Due Date approach is not ideal because it fails to find a feasible schedule of visits in many instances when a feasible schedule is possible. The Due Date algorithm is provided below in pseudocode.                1. Initially, the variable that keeps track of the iterations, j, is set to 0. Set ri0=ui, i=1, . . . , n.        2. Select the job with the smallest residual time. Let k=miniri, i=1, . . . , n.        3. Increase the iteration variable j by 1, j=j+1;        
      r    i    j    =      {                                                                      u                k                            ,                        ⁢                                                                                                                                      if                  ⁢                                                                          ⁢                  i                                =                k                            ;                        ⁢                                                                                                                                r                i                            -                              τ                i                                      ,                                                otherwise            .                                              4. Check to see if rij≧0, i=1, . . . , n. If yes, then go to Step 2. If no, then the Due Date algorithm does not produce a feasible schedule of visits.        
Consider the following example: τ1=1, τ2=2, τ3=3, and μ1=4, μ2=5, μ3=4. By choosing the job with the smallest residual time and breaking ties by considering the duration time τi, the following sequence of jobs is obtained: 1, 3, 1, 2, 3. The sequence of jobs is obtained as follows. The initial residual vector is (4, 5, 4). Because there is a tie in residual times between jobs 1 and 3, job 1 is chosen because it has a shorter duration of 1, whereas job 3 has a duration of 3. The residual vector becomes (4, 4, 3) after choosing job 1 (i.e., 4, 5−1, 4−1). It becomes (1, 1, 4) after visiting location 3, (4, 0, 3) after visiting location 1, (2, 5, 1) after visiting location 2, and (−1, 2, 4) after visiting location 3 again. A negative value indicates that a job was not performed within the revisit time μi. As mentioned previously, the revisit time μi is a hard constraint. Although the Due Date approach failed to find a feasible schedule of visits, a feasible schedule for this example does exist: 1, 2, 1, 3, 1, 2, etc. . . . (repeating).
Unlike the Due Date approach, the Critical Ratio approach makes use of all of the information available to decide which location to visit next. However, it also is not ideal because it fails to find a feasible schedule of visits in many instances when a feasible schedule is possible. With each transition of the Critical Ratio approach, an auxiliary vector is formed. The auxiliary vector consists of the following ratios:
      k    =                  min        i            ⁢                                    r            i                    +                      τ            i                                                μ            i                    +                      τ            i                                ,      i    =    1    ,  …  ,      n    .  where i=1, . . . , N. Under the Critical Ratio approach, the job that is going to expire the soonest (i.e., the job with the smallest ratio in the auxiliary vector) is selected. While the Critical Ratio heuristic addresses some of the problems associated with the Due Date approach, it is not a complete solution. The Critical Ratio algorithm is provided below in pseudo-code.                1. Initially, the variable that keeps track of the iterations, j, is set to 0. Set ri0=ui, i=1, . . . , n.        2. Select the job with the smallest value of        
                    r        i            +              τ        i                            μ        i            +              τ        i              .Let
                    r        i            +              τ        i                            μ        i            +              τ        i              ,                3. Increase the iteration variable j by 1, j=j+1;        
      r    i    j    =      {                                                                      u                k                            ,                        ⁢                                                                                                                                      if                  ⁢                                                                          ⁢                  i                                =                k                            ;                        ⁢                                                                                                                                r                i                            -                              τ                i                                      ,                                                otherwise            .                                              4. Check to see if rij≧0, i=1, . . . , n. If yes, then go to Step 2. If no, then the Critical Ratio algorithm does not produce a feasible schedule of visits.        
Consider the same example used for the Due Date approach above: τ1=1, τ2=2, τ3=3, and μ1=4, μ2=5, μ3=4. By choosing the job with the smallest ratio in the auxiliary vector and arbitrarily breaking ties, two infeasible sequences may be generated: 1, 2, 3 and 1, 3, 1, 2, 3. It is assumed that the initial residual vector contains all zeros. The sequences of visits are obtained as follows. The initial residual vector is (0, 0, 0). The initial auxiliary vector is (1/5, 2/7, 3/7) The smallest ratio in the initial auxiliary vector is for job 1. The residual vector becomes (4, 4, 3) after choosing job 1 (i.e., 4, 5−1, 4−1). The auxiliary vector becomes (5/5, 6/7, 6/7).
Now there is a tie between the ratios of jobs 2 and 3. If job 2 is chosen, the residual vector becomes (2, 5, 1) and the auxiliary vector becomes (3/5, 7/7, 4/7). Job 3 is then chosen and the residual vector becomes (−1, 2, 4). The algorithm terminates because of the negative value in the residual vector. If job 3 is chosen, the residual vector becomes (1, 1, 4) and the auxiliary vector becomes (3/5, 7/7, 4/7). When job 1 is chosen next, the residual vector becomes (4, 0, 3) and the auxiliary vector becomes (5/5, 2/7, 6/7). When job 2 is chosen next, the residual vector becomes (2, 5, 1) and the auxiliary vector becomes (3/5, 7/7, 4/7). Job 3 is then chosen and the residual vector becomes (−1, 2, 4). The algorithm terminates because of the negative value in the residual vector. Accordingly, the Critical Ratio approach fails to find the feasible schedule of visits of 1, 2, 1, 3, 1, 2, etc. . . . (repeating), as shown earlier.
The DP algorithm is proven to be unworkable because it requires exponential resources. The Due Date and Critical Ratio approaches fail to find a feasible schedule of visits in many instances, such as the examples shown earlier. Therefore, a need exists for an approach that finds a feasible schedule of visits for most, if not all, instances with n jobs given a duration, τi, and a revisit time, μi. The algorithm should make use of all of the information available at the time the decision is to be made.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.